﻿//BC157 素数回文（模拟+数学）
//https://www.nowcoder.com/practice/d638855898fb4d22bc0ae9314fed956f?tpId=290&tqId=39945&ru=/exam/oj

//#include <iostream>
//#include <string>
//#include <cmath>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//    for (int i = s.size() - 2; i >= 0; i--)
//    {
//        s += s[i];
//    }
//    long long num = stol(s);
//
//    bool flag = true;
//    for (int i = 2; i < sqrt(num); i++)
//    {
//        if (num % i == 0)
//            flag = false;
//    }
//    cout << (flag ? "prime" : "noprime") << endl;
//    return 0;
//}


//AB31 活动安排 （贪⼼-区间）
//https://www.nowcoder.com/practice/16d971e9e42e4f3b9b1e2b8794796a43?tpId=308&tqId=40488&ru=/exam/oj

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<pair<int, int>> v;
//    for (int i = 0; i < n; i++)
//    {
//        int first, second;
//        cin >> first >> second;
//        v.emplace_back(first, second);
//    }
//    sort(v.begin(), v.end());
//    int ret = 1, time = v[0].second;
//    for (int i = 1; i < n; i++)
//    {
//        if (time <= v[i].first)
//        {
//            ret++;
//            time = v[i].second;
//        }
//        else
//        {
//            time = min(time, v[i].second);
//        }
//    }
//    cout << ret << endl;
//}

//合唱团（动态规划-线性dp）
//https://www.nowcoder.com/practice/661c49118ca241909add3a11c96408c8?tpId=122&tqId=33652&ru=/exam/oj

//f[i][j] 从前i个人中选j个人，第j个人必选，最大乘积
//g[i][j] 从前i个人中选j个人，第j个人必选，最小乘积(负数*最小=最大)
//max(i-d,j-1) <= prev <= i-1
//f[i][j]=max(arr[i]*f[prev][j-1],arr[i]*g[prev][j-1]) 
//g[i][j]=min(arr[i]*f[prev][j-1],arr[i]*g[perv][j-1])


//#include <iostream>
//using namespace std;
//
//const int N = 55, M = 15;
//
//long long f[N][M], g[N][M];
//int arr[N];
//int n, k, d;
//
//int main() {
//    cin >> n;
//    for (int i = 1; i <= n; i++)cin >> arr[i];
//    cin >> k >> d;
//
//    //初始化
//    for (int i = 1; i <= n; i++)
//    {
//        f[i][1] = g[i][1] = arr[i];
//        for (int j = 2; j <= min(i, k); j++)
//        {
//            f[i][j] = -0x3f3f3f3f3f3f3f3f;
//            g[i][j] = 0x3f3f3f3f3f3f3f3f;
//        }
//    }
//    
//
//    for (int i = 2; i <= n; i++)
//    {
//        for (int j = 2; j <= min(i, k); j++)
//        {
//            for (int prev = max(i - d, j - 1); prev <= i - 1; prev++)
//            {
//                f[i][j] = max(max(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), f[i][j]);
//                g[i][j] = min(min(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), g[i][j]);
//            }
//        }
//    }
//
//    long long ret = -0x3f3f3f3f3f3f3f3f;
//    for (int i = k; i <= n; i++)
//    {
//        ret = max(f[i][k], ret);
//    }
//    cout << ret << endl;
//
//    return 0;
//}